/*
 * CopyRight(C) Kenbin
 */

#include "lws_wordgraph.h"
#include <stdio.h>
#include <cfloat>
#include <algorithm>

void LWS::CWordGraph::Init(int total_node)
{
    m_word_graph.resize(total_node);
    for(int i = 0; i < total_node; i ++) {
	m_word_graph[i].resize(0);
    }

    GraphNode node;
    node.pre_node = -1;
    node.word_id = -1;
    node.word_prob = 0;

    m_word_graph[0].push_back(node);
}

void LWS::CWordGraph::AddWord(int first_CHAR_pos, int last_CHAR_pos, int word_id, float word_prob)
{
    GraphNode node;
    node.pre_node = first_CHAR_pos;
    node.word_id = word_id;
    node.word_prob = word_prob;

    /* last_CHAR_pos+1 is the next word's first_CHAR_pos */
    m_word_graph[last_CHAR_pos+1].push_back(node);
}

void LWS::CWordGraph::GenerateBestPath()
{
    for(unsigned i = 1; i < m_word_graph.size(); i ++) {
	float best_prob = FLT_MAX;
	int best_node, best_wordid;

	for(unsigned j = 0; j < m_word_graph[i].size(); j ++) {
	    int pre_node = m_word_graph[i][j].pre_node;
	    float accum_prob = m_word_graph[i][j].word_prob + m_word_graph[pre_node][0].word_prob;

	    if(accum_prob < best_prob) {
		best_node = pre_node;
		best_wordid = m_word_graph[i][j].word_id;
		best_prob = accum_prob;
	    }
	}

	m_word_graph[i][0].pre_node = best_node;
	m_word_graph[i][0].word_id = best_wordid;
	m_word_graph[i][0].word_prob = best_prob;
    }

    m_best_node_path.resize(0);
    m_best_wordid_path.resize(0);

    int n = m_word_graph.size() - 1;
    while(n >= 0) {
	m_best_node_path.push_back(n);
	m_best_wordid_path.push_back(m_word_graph[n][0].word_id);
	n = m_word_graph[n][0].pre_node;
    }

    reverse(m_best_node_path.begin(), m_best_node_path.end());

    m_best_wordid_path.pop_back(); /* the last graphnode is not a word,but the lastword's next */
    reverse(m_best_wordid_path.begin(), m_best_wordid_path.end());
}

void LWS::CWordGraph::Print()
{
    for(unsigned i = 0; i < m_word_graph.size(); i ++) {
	if(i < 10) {
	    printf("%d  : ", i);
	} else {
	    printf("%d : ", i);
	}

	for(unsigned j = 0; j < m_word_graph[i].size(); j ++) {
	    printf("[%d %d %f] ", m_word_graph[i][j].pre_node, m_word_graph[i][j].word_id,
		    m_word_graph[i][j].word_prob);
	}
	printf("\n");
    }
}
